package _dp_base;

/**
 * 1035. 不相交的线
 */
public class No1035 {
    private int[] nums1, nums2;

    /**
     * 1. 递归
     */
    public int maxUncrossedLines1(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        int n = nums1.length;
        int m = nums2.length;
        return dfs(n - 1, m - 1);
    }

    private int dfs(int i, int j) {
        if (i < 0 || j < 0) return 0;
        else if (nums1[i] == nums2[j]) return dfs(i - 1, j - 1) + 1;
        else return Math.max(dfs(i - 1, j), dfs(i, j - 1));
    }

    /**
     * 2. 迭代
     */
    public int maxUncrossedLines2(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nums1[i] == nums2[j]) f[i + 1][j + 1] = f[i][j] + 1;
                else f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
            }
        }
        return f[n][m];
    }

    /**
     * 4. 空间优化
     */
    public int maxUncrossedLines4(int[] nums1, int[] nums2) {
        int m = nums2.length;

        int[] f = new int[m + 1];
        for (int k : nums1) {
            int pre = f[0];
            for (int j = 0; j < m; j++) {
                int temp = f[j + 1];
                if (k == nums2[j]) f[j + 1] = pre + 1;
                else f[j + 1] = Math.max(f[j + 1], f[j]);
                pre = temp;
            }
        }
        return f[m];
    }
}
